package knapsack

import "math"

func (kd * KnapsackData) NextSize (ii int, old_size []int) (new_size []int) {
	dim := kd.Dim
	new_size = make ([]int, dim)
	copy (new_size, old_size)
      var i int
	for i = dim - 1; i >= 0; i -- {
		new_size[i] ++
		if (new_size[i] <= kd.limit[i]) { 
			break 
		} else {
			new_size[i] = 0
		}
	}
	if (i < 0) {
		return make ([]int, 0)
	} else {
		return new_size
	}
}

func InitKnapsackData (reduce_method int, dim int, num_item int) * KnapsackData {

	if (dim < 0 || dim > 5 || num_item < 1) {
		panic ("wrong knapsack options")
	}

	var kd KnapsackData 

	kd.reduce_method = reduce_method

	kd.Dim = dim
	kd.Num = num_item
	kd.limit_coef = make ([][]int, dim)
	for i := 0; i < dim; i ++ {
		kd.limit_coef[i] = make ([]int, num_item)
	}
	kd.limit = make ([]int, dim)
	kd.util = make ([]UtilFunction, num_item)
      for i := 0; i < num_item; i ++ {
		kd.util[i] = ZeroUtilFunc
	}

      kd.sel_ = make ([]int, 0)
      kd.new_sel_ = make ([]int, 0)
	kd.value_ = make ([]float64, 0)

      kd.sel = make ([][]int, 0)
      kd.new_sel = make ([][]int, 0)
	kd.value = make ([][]float64, 0)

	kd.final_sel = make ([]int, num_item)
	for i := 0; i < num_item; i ++ {
		kd.final_sel[i] = -1
	}

	return &kd
}

func (kd * KnapsackData) SetUtil (ii int, util_func UtilFunction) {
	kd.util[ii] = util_func
}

func (kd * KnapsackData) SetLimit (limit_coef [][]int, limit []int) {

      dim := kd.Dim
      num := kd.Num

	for i := 0; i < dim; i ++ {
		copy (kd.limit_coef[i], limit_coef[i][0:num])
	}
	copy (kd.limit, limit[0:dim])

      kd.total_size = 1
      for i := 0; i < dim; i ++ {
            kd.total_size *= kd.limit[i] + 1
      }

	kd.sel_ = make ([]int, num * kd.total_size)
	kd.new_sel_ = make ([]int, num * kd.total_size)
	kd.value_ = make ([]float64, num * kd.total_size)

      kd.sel = make([][]int, num)  
      kd.new_sel = make([][]int, num)
      kd.value = make([][]float64, num)  
	for j := 0; j < num; j ++ {
		kd.sel[j] = kd.sel_[j * kd.total_size : (j + 1) * kd.total_size]
		kd.new_sel[j] = kd.new_sel_[j * kd.total_size : (j + 1) * kd.total_size]
		kd.value[j] = kd.value_[j * kd.total_size : (j + 1) * kd.total_size]
	}

}

func (kd * KnapsackData) GetMaxSelectable (ii int) int {
	min_xii := -1
	for i := 0; i < kd.Dim; i ++ {
		new_min_xii := kd.limit[i] / kd.limit_coef[i][ii]
		if (min_xii == -1 ||  new_min_xii < min_xii) {
			min_xii = new_min_xii
		}
	}
	return min_xii
}

func (kd * KnapsackData) SolveStep (ii int) {
	dim := kd.Dim
	num := kd.Num

	xiimax := kd.GetMaxSelectable (ii)
	var ck []float64 = make ([]float64, xiimax + 1)
	for i := 0; i <= xiimax; i ++ {
		ck[i] = kd.util[ii] (i)
	}

	for size := make ([]int, dim); len(size) != 0; size = kd.NextSize (ii, size) {
		if (ii == num - 1) { 
			copy (size, kd.limit) 
		}
		ind := kd.size2ind (size)
		pv := &kd.value[ii][ind] 

		min_xii := -1
		for i := 0; i < dim; i ++ {
                  new_min_xii := size[i] / kd.limit_coef[i][ii]
			if (min_xii == -1 ||  new_min_xii < min_xii) {
                        min_xii = new_min_xii
			}
		}

		*pv = 0
		var new_ind_max int
		var xii_max int
		for xii := 0; xii <= min_xii; xii ++ {
                  new_size := make ([]int, dim)
                  copy (new_size, size)
                  for i := 0; i < dim; i ++ {
                        new_size[i] -= xii * kd.limit_coef[i][ii]
                  }
			new_ind := kd.size2ind(new_size)

                  var newv float64
                  if (ii == 0) {
                        newv = ck[xii]
                  } else {
				switch kd.reduce_method {
				case RM_SUM:
					newv = ck[xii] + kd.value[ii - 1][new_ind]
				case RM_MULTI:
					newv = ck[xii] * kd.value[ii - 1][new_ind]
				case RM_MAX:
					newv = math.Max (ck[xii], kd.value[ii - 1][new_ind])
				case RM_MIN:
					newv = math.Min (ck[xii], kd.value[ii - 1][new_ind])
				default:
					panic ("wrong reduce method.")
				}
                  }
                  if (xii == 0 || newv > *pv) {
                        *pv = newv
				xii_max = xii
				new_ind_max = new_ind
                  }
		}

		for i := 0; i < ii; i ++ {
			kd.new_sel[i][ind] = kd.sel[i][new_ind_max]
		}
		kd.new_sel[ii][ind] = xii_max
	}

	if (ii == num - 1) { 
		for i := 0; i < num; i ++ {
			kd.final_sel[i] = kd.new_sel[i][kd.total_size - 1]
		}
	} else {
		copy (kd.sel_[:(ii + 1) * kd.total_size], kd.new_sel_[:(ii + 1) * kd.total_size])
	}
}

func (kd * KnapsackData) Solve () {
      for ii := 0; ii < kd.Num; ii ++ {
            kd.SolveStep (ii)
      }
}
